#[test]
fn test_word_break() {
    assert!(word_break(
        "leetcode".to_string(),
        vec!["leet".to_string(), "code".to_string()]
    ));

    assert!(word_break(
        "applepenapple".to_string(),
        vec!["apple".to_string(), "pen".to_string()]
    ));

    assert!(!word_break(
        "catsandog".to_string(),
        vec![
            "cats".to_string(),
            "dog".to_string(),
            "sand".to_string(),
            "and".to_string(),
            "cat".to_string()
        ]
    ));
}

/*
139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。

示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
*/
pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
    let word_set: std::collections::HashSet<String> = word_dict.into_iter().collect();
    let len = s.len();
    let mut dp = vec![false; len + 1];
    dp[0] = true;
    for i in 1..=len {
        for j in (0..i).rev() {
            if dp[j] && word_set.contains(&s[j..i].to_string()) {
                dp[i] = true;
                break;
            }
        }
    }
    dp[len]
}
